﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0141_SerializeTreeNode : IAlgorithm
    {
        // 二叉树的序列化与反序列化

        // 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，
        // 采取相反方式重构得到原数据。
        // 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个
        // 字符串反序列化为原始的树结构。

        // 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

        // 提示：
        //  树中结点数在范围[0, 10^4] 内
        //  -1000 <= Node.val <= 1000

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public class Codec
        {
            private const string NULL = "#";
            private const string SEP = ",";

            // Encodes a tree to a single string.
            public string serialize(TreeNode root)
            {
                StringBuilder sb = new StringBuilder();
                serialize(root, sb);
                return sb.ToString();
            }

            private void serialize(TreeNode root, StringBuilder sb)
            {
                if (root == null)
                {
                    sb.Append(NULL).Append(SEP);
                    return;
                }
                sb.Append(root.val).Append(SEP);

                serialize(root.left, sb);
                serialize(root.right, sb);
            }

            // Decodes your encoded data to tree.
            public TreeNode deserialize(string data)
            {
                var nodes = data.Split(SEP).ToList();
                return deserialize(nodes);
            }

            private TreeNode deserialize(List<string> nodes)
            {
                if (nodes.Count == 0)
                {
                    return null;
                }
                var val = nodes.First();
                nodes.Remove(val);
                if (NULL.Equals(val))
                    return null;
                TreeNode root = new TreeNode(int.Parse(val))
                {
                    left = deserialize(nodes),
                    right = deserialize(nodes)
                };
                return root;
            }
        }
    }
}
